1. Field of the Invention
The invention deals with systems in which data is communicated among a plurality of devices, and in particular with methods and apparatus for routing data on such systems.
2. Related Art
Systems which communicate data from one device to another typically route the data from a source to a destination along a route determined independently each time data is transmitted or determined in advance irrespective of dynamic traffic loads on a network. Such systems generally give no consideration to how data has previously been routed. For example, FIG. 1 illustrates an arbitrary configuration of a network with devices 101, 103, 105, and 107. The devices communicate over lines connected to information transfer points 109, 111, 113, and 115. In routing a message from device 101 to 105, several options are available. For example, a message can leave device 101 on signal line 117 and at node 109 be transferred to signal line 119 for routing to device 105. Alternatively, at node 109 the message can be routed on signal line 121 to node 111, which then transmits the message on signal line 123 to node 113 for transmission on line 125 to node 105. Alternatively, node 111 can transmit the same message on signal line 127 to node 115, which passes the message on signal line 129 to node 105. Other alternative paths may also be available, depending on the present traffic on the network. As networks become more sophisticated involving additional devices and data transfer points, the routing decisions become more complex.
Conventionally, device 101 transmits its message using some method to determine an available transmit path to device 105 without any significant consideration of where device 105 is located on the network. Typically, device 101 looks for an available transmit path and leaves it up to device 105 to recognize the message and respond. Device 105 may receive the message quickly or slowly depending on the traffic and the route taken. If the message travels a circuitous route, its presence on the network consumes bandwidth that can be better utilized for other purposes. Thus, conventional systems which route information based on the availability of transmission resources at each of the data transfer points alone, may be highly inefficient.